package lab2;

import java.lang.reflect.InvocationTargetException;
import java.util.Comparator;
import java.util.RandomAccess;

public final class MyCollections {

	private MyCollections() {

	}

	@SuppressWarnings({ "unchecked" })
	private static <T> void quickSortComparable(final MyList<? extends Comparable<? super T>> list, final int low, final int high) {
		int i = low, j = high;
		Comparable<? super T> pivot = list.get(low + (high - low) / 2);
		while (i <= j) {
			while (list.get(i).compareTo((T) pivot) < 0) {
				i++;
			}
			while (list.get(j).compareTo((T) pivot) > 0) {
				j--;
			}
			if (i <= j) {
				swap(list, i, j);
				i++;
				j--;
			}
		}

		if (low < j) {
			quickSortComparable(list, low, j);
		}
		if (i < high) {
			quickSortComparable(list, i, high);
		}
	}

	private static <T> void quickSortComparator(final MyList<T> list, final int low, final int high, final Comparator<T> c) {
		int i = low, j = high;
		T pivot = list.get(low + (high - low) / 2);
		while (i <= j) {
			while (c.compare(list.get(i), pivot) < 0) {
				i++;
			}
			while (c.compare(list.get(j), pivot) > 0) {
				j--;
			}
			if (i <= j) {
				swap(list, i, j);
				i++;
				j--;
			}
		}

		if (low < j) {
			quickSortComparator(list, low, j, c);
		}
		if (i < high) {
			quickSortComparator(list, i, high, c);
		}
	}

	@SuppressWarnings("unchecked")
	private static <T> void bubbleSortComparable(final MyList<? extends Comparable<? super T>> list) {
		boolean swapOccured;

		do {
			swapOccured = false;

			for (int i = 0; i < (list.size() - 1); i++) {
				if (list.get(i).compareTo((T) list.get(i + 1)) > 0) {
					swap(list, i, i + 1);
					swapOccured = true;
				}
			}
		}
		while (swapOccured);
	}

	private static <T> void bubbleSortComparator(final MyList<T> list, final Comparator<T> c) {
		boolean swapOccured;

		do {
			swapOccured = false;

			for (int i = 0; i < (list.size() - 1); i++) {
				if (c.compare(list.get(i), list.get(i + 1)) > 0) {

					swap(list, i, i + 1);

					swapOccured = true;
				}
			}
		}
		while (swapOccured);
	}

	public static <T> void sort(final MyList<? extends Comparable<? super T>> list) {

		if (list instanceof RandomAccess) {
			quickSortComparable(list, 0, list.size() - 1);
		} else {
			bubbleSortComparable(list);
		}
	}

	public static <T> void sort(final MyList<T> list, final Comparator<T> c) {

		if (list instanceof RandomAccess) {
			quickSortComparator(list, 0, list.size() - 1, c);
		} else {
			bubbleSortComparator(list, c);
		}
	}

	public static <T> void swap(final MyList<T> list, final int i, final int j) {
		if (i < 0 || i >= list.size()) {
			throw new MyIndexOutOfBoundsException("Index out of bounds!");
		}

		if (j < 0 || j >= list.size()) {
			throw new MyIndexOutOfBoundsException("Index out of bounds!");
		}

		T temp = list.get(i);
		list.set(i, list.get(j));
		list.set(j, temp);
	}

	public static <T> void copy(final MyList<T> dest, final MyList<T> src) {
		dest.addAll(src.toArray());
	}

	public static <T> void reverse(final MyList<T> list) {
		for (int i = 0; i < list.size() / 2; i++) {
			swap(list, i, list.size() - 1 - i);
		}
	}

	public static int binarySearch(final RandomAccess list, final Object key) {

		Integer length = new Integer(0);
		try {
			length = (Integer) list.getClass().getMethod("size").invoke(list, null);
		} catch (IllegalAccessException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IllegalArgumentException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (InvocationTargetException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (NoSuchMethodException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (SecurityException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

		return bisection(list, key, 0, length - 1);
	}

	private static int bisection(final RandomAccess list, final Object key, final int low, final int high) {
		int median = (low + high) / 2;

		Object finding = new Object();
		try {
			finding = list.getClass().getMethod("get", int.class).invoke(list, median);
		} catch (IllegalAccessException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IllegalArgumentException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (InvocationTargetException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (NoSuchMethodException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (SecurityException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

		if (finding.equals(key)) {
			return median;
		}

		if (low == high) {
			return (median * (-1) - 1);
		}

		Integer comparationResult = 0;

		try {
			comparationResult = (Integer) finding.getClass().getMethod("compareTo", finding.getClass()).invoke(finding, key);
		} catch (IllegalAccessException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (IllegalArgumentException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (InvocationTargetException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (NoSuchMethodException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		} catch (SecurityException e) {
			// TODO Auto-generated catch block
			e.printStackTrace();
		}

		if (comparationResult < 0) {
			return bisection(list, key, median + 1, high);
		} else {
			return bisection(list, key,  0, median - 1);
		}
	}
}
